package algorithm;


/**
 * 检测链表中是否有环
 */
public class T00141 {
    public static void main(String[] args) {
        ListNode node = build(1, 3,2,0,-4);
        System.out.println(new Solution().hasCycle(node));
    }

    static ListNode build(int pos, int... arr) {
        if(arr == null || arr.length == 0)
            return null;
        ListNode head = new ListNode(arr[arr.length - 1]);
        if(arr.length == 1)
            return head;

        ListNode tail = head;
        for (int i = arr.length - 2; i >= 0; i --) {
            ListNode t = new ListNode(arr[i]);
            if(pos != -1 && arr.length - i - 2 == pos)
                tail.next = t;
            t.next = head;
            head = t;
        }
        return head;
    }

static class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null)
            return false;
        ListNode slow = head, fast = slow;
        while(true) {
            fast = fast.next;
            if(fast == null || fast.next == null)
                return false;
            fast = fast.next;
            if(fast == slow || fast == slow.next)
                return true;
            slow = slow.next;
        }
    }
}

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}